package q208;

import java.util.HashSet;
import java.util.Set;

/**
 * 208. 实现Trie（前缀树）
 */
public class Trie {

    TrieNode root;

    public static class TrieNode {
        char c;
        boolean isWord;
        Set<TrieNode> nextChars;

        TrieNode() {
            this.c = '\0';
            this.nextChars = new HashSet<>();
            isWord = false;
        }
    }

    public Trie() {
        root = new TrieNode();
    }

    public void insert(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);

            boolean find = false;
            for (TrieNode children : node.nextChars) {
                if (children.c == c) {
                    node = children;
                    find = true;
                    break;
                }
            }

            if (!find) {
                TrieNode trieNode = new TrieNode();
                trieNode.c = c;
                node.nextChars.add(trieNode);
                node = trieNode;
            }
        }
        node.isWord = true;
    }

    public boolean search(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            boolean find = false;
            for (TrieNode children : node.nextChars) {
                if (children.c == c) {
                    node = children;
                    find = true;
                    break;
                }
            }
            if (!find) return false;
        }
        return node.isWord;
    }

    public boolean startsWith(String prefix) {
        TrieNode node = root;
        for (int i = 0; i < prefix.length(); i++) {
            char c = prefix.charAt(i);
            boolean find = false;
            for (TrieNode children : node.nextChars) {
                if (children.c == c) {
                    node = children;
                    find = true;
                    break;
                }
            }
            if (!find) return false;
        }
        return true;
    }
    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("abc");
        trie.search("abc");
        System.out.println(trie.search("abc"));
    }
}
